// m
// 给定一个升序数组nums和一个目标值target，找出给定目标值在数组中的开始位置和结束位置，要求使用时间复杂度为O(logn)


// 思路：时间复杂度为O(logn)，那么就需要用二分查找算法了
// 进行两次二分查找，第一次尽量向左搜索，第二次尽量向右搜索

function searchRange(nums, target) {
    let ans = [-1, -1]
    let size = nums.length
    if (size === 0) {
        return ans
    }
    let left = 0
    let right = size - 1
    while (left < right) {
        let mid = Math.floor((right - left) / 2) + left
        if (nums[mid] < target) {
            left = mid + 1
        } else {
            right = mid
        }
    }
    if (nums[left] !== target) {
        return ans
    }
    ans[0] = left

    left = 0
    right = size - 1
    while (left < right) {
        let mid = Math.floor((right - left + 1) / 2) + left
        if (nums[mid] > target) {
            right = mid - 1
        } else {
            left = mid
        }
    }
    if (nums[left] === target) {
        ans[1] = left
    }
    return ans
}

let arr = [1, 2, 2, 3, 3, 3, 3, 3, 7]
console.log(searchRange(arr, 2));